// packrat.hpp
// Implementation of the packrat parser (with support for direct left
// recursion).
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#ifndef R_PACKRAT_HPP
#define R_PACKRAT_HPP

#include "util/standard.hpp"
#include "util/token.hpp"
#include "adts/vector.hpp"
#include "adts/map.hpp"

namespace Ripe {
  // A nonterminal in the grammar.
  typedef uint32_t Nonterminal;

  // State in packrat parser. (TODO: This is a bad solution. Improve.)
  typedef uint32_t State;

  // A semantic value of a given grammar match.
  typedef void* Semantic;

  // A pointer to a recursive descent matching function.
  class Parsing;
  typedef Semantic (*Matcher) (Parsing*, int precedence);

  // Key in the memo table.
  struct MemoKey {
    Nonterminal nonterm;
    uint32_t location;

    // Must implement an equality operator because of the Map data structure.
    bool operator==(const MemoKey& other);
  };

  // Status of a match in the memo table.
  enum MemoStatus {
    StatusApplying,
    StatusDetectedLR,
    StatusApplied
  };

  // Value in the memo table.
  struct MemoValue {
    MemoStatus status;
    Semantic ast;
    uint32_t new_idx;
  };

  // One run of the parser.
  class Parsing {
    public:
      // Associated grammar.
      Map<Nonterminal, Matcher> grammar;

      // Tokens being parsed.
      Vector<Token*>* tokens;

      // Expect a token of this type. If found, consume it and return its extra
      // pointer. Return true if token consumed (idx increased). Otherwise,
      // return false (idx remains the same).
      bool consume(uint32_t type, Token** extra);

      // Match a single rule at parsing->idx in the stream. If the match fails,
      // rewind the stream.
      Semantic match(Nonterminal nterm, int precedence);

      // Initiate parsing and return a semantic value (most likely the AST)
      // obtained after matching the start symbol at the beggining of the token
      // list.
      Semantic parse(Nonterminal start);

      // Read one token from the input (and consume it). If there are no more
      // tokens, return false.
      bool read(Token** extra);

      // Save the current index, in case matching this rule fails.
      State save();

      // Restore a saved index, since matching some rule failed.
      void restore(State state);

    private:
      // Apply the rule for the given nonterminal by finding the match function
      // in the grammar.
      Semantic apply(Nonterminal nterm, int precedence);

      // Current place in the stream
      uint32_t idx;

      // Memoization table.
      Map<MemoKey, MemoValue> memo;
  };
}

#endif // R_PACKRAT_HPP
